import collections
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        m = len(s)
        n = len(p)
        if m < n:
            return []
        out = []
        dict_p = collections.defaultdict(int)
        for item in p:
            dict_p[item] += 1
        for i in range(n):
            dict_p[s[i]] -= 1
            if dict_p[s[i]] == 0:
                dict_p.pop(s[i])
        if not dict_p:
            out.append(0)
        for i in range(n, m):
            dict_p[s[i - n]] += 1
            if dict_p[s[i - n]] == 0:
                dict_p.pop(s[i - n])
            dict_p[s[i]] -= 1
            if dict_p[s[i]] == 0:
                dict_p.pop(s[i])
            if not dict_p:
                out.append(i - n + 1)
        return out


data = Solution()
s = "aaaaa"
p = "aaaaaaaa"
print(data.findAnagrams(s, p))
